//并查集


//* 路径压缩和按照rank合并应该二选一就行,两个都有的话,感觉有点多余
export class UnionFind{
    //每个点的父节点
    private parent:number[] 
    //每个点的孩子节点的深度
    private level:number[]
    constructor(n:number){
        this.parent = new Array<number>(n).fill(0)
        this.level = new Array<number>(n).fill(0)
        // 做自己的parent
        this.parent.forEach((_,i,arr)=>arr[i]=i) 
    }

    //合并两个
    public union(x:number,y:number){
        if(x===y) return ;
        const px = this.find(x)
        const py = this.find(y)
        if(this.level[px]>this.level[py]){
            this.parent[py] = px
        }else if(this.level[px]<this.level[py]){
            this.parent[px] = py
        }else{
            // 层次发生变化
            this.parent[px] = py
            this.level[py]++
        }
    }

    // 带路径压缩的查找
    public find(x:number):number{
        while(this.parent[x]!=x){
            //边找边路径压缩
            this.parent[x] = this.parent[this.parent[x]]
            x = this.parent[x]
        }
        return x
    }

    //返回root的点
    public getRoot():number[]{
        const root:number[] = []
        this.parent.forEach((e,i)=>e===i&&root.push(i))
        return root
    }
}


// 547. 省份数量
function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length
    const uf = new UnionFind(n)
    for(let i=0;i<n;i++){
        for(let j=i+1;j<n;j++){
            if(isConnected[i][j]){
                uf.union(i,j)
            }
        }
    }
    return uf.getRoot().length
};